package net.sourceforge.wurfl.core.handlers.matchers.strategy.trie;

import java.util.Iterator;

import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.build.DataProvider;
import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.node.CharTrieNode;
import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.node.TrieNode;


/**
 * A Patricia Trie is a particular trie implementation in which paths from deepest branchings and leaves
 * are compressed in only one node if every node of that path has exactly one child 
 * @author WURFL-PRO SRL, Rome, Italy
 */
public class PatriciaTrie implements Trie {
	
	private TrieNode root;
	
	public PatriciaTrie() {
		this.setRoot(new CharTrieNode(new Character('_')));
	}

	public PatriciaTrie(DataProvider dataProvider) {
		this.setRoot(new CharTrieNode(new Character('_')));
		for (Iterator dataIterator = dataProvider.getData().iterator();dataIterator.hasNext();) {
			this.put(dataIterator.next());
		}
	}
	

	/** 
	 * search for an Object with the specified String key
	 */
	public Object search(String key) {
		String keyString = key.toString();
		return get(this.getRoot(), keyString, 0);
	}
	
	public Object search(String key, Integer tolerance) {
		// TODO Auto-generated method stub
		return null;
	}
	
	/** 
	 * recursive searching method
	 * @param node
	 * @param keyString
	 * @param index
	 * @return
	 */
	private Object get(TrieNode node, String keyString, int index) {
		Object value = null;
		if (index == keyString.length()) {
			value = node.getValue();
		} 
		else if (keyString.equals(""+node.getValue())){
			value = node.getValue();
		} 
		else if (keyString.length()>index){
			Character c = new Character(keyString.charAt(index));
			CharTrieNode childNode = (CharTrieNode) node.getSubTrie().get(c);
			value = get(childNode, keyString, index + 1);
		}
		
		return value;
	}
	
	
	
	
	/**
	 * put an Object into the Trie 
	 */
	public void put(Object object) {
		this.insert(object.toString(), 0, this.getRoot());
	}

	/** recursive sliding window put method */
	private void insert(String data, int index, TrieNode trieNode) {
		if (data != null && data.length()>index) {
			Character toInsert = new Character(data.charAt(index));
			CharTrieNode selectedNode = (CharTrieNode) trieNode.getSubTrie().get(toInsert);

			if (selectedNode == null) {
				selectedNode = new CharTrieNode(toInsert);
				selectedNode.setValue(data);
				selectedNode.setTolerance(new Integer(index+1));
				trieNode.getSubTrie().put(toInsert, selectedNode);
			}
			else {
				Object val = selectedNode.getValue();
				if (val!=null && val.toString().length()>(index+1) && val.toString().charAt(index)==toInsert.charValue()) {
					CharTrieNode newNode = new CharTrieNode(new Character(val.toString().charAt(index+1)));
					newNode.setValue(val);
					selectedNode.setValue(null);
					selectedNode.getSubTrie().put(new Character(val.toString().charAt(index+1)), newNode);
				}
				insert(data, index+1, selectedNode);
			}
		} else {
			trieNode.setValue(data);
		}

	}
	
	
	
	

	public void setRoot(TrieNode root) {
		this.root = root;
	}

	public TrieNode getRoot() {
		return root;
	}

}
